The present invention relates generally to the optimization of finite state machines (FSMs) synthesized from hierarchical high-level descriptions. More specifically, the present invention relates to determining partitions of a hierarchical high-level description which will lead to greater optimization when synthesized into an FSM.
To tackle the exponential growth in the complexity of digital circuits, designers are moving to higher levels of abstraction in the design process. In control dominated applications, several abstractions are popular for managing the complexity of the design of sequential control logic. These techniques use an input language whose level of abstraction is above explicit FSM (finite state machine) design techniques that use state transition tables or RTL (register transfer level) HDL (hardware description language) descriptions.
In these abstractions, the high-level controller description is typically described in a hierarchical fashion as depicted by the tree in FIG. 1. The nodes of the tree, which are stored in the memory of a data processing system, represent the compositional operators of the control abstraction. For example, a particular node might indicate the sequencing or the concurrent execution of the sub-behaviors represented by the node""s children (or sub-nodes).
Synthesis of circuits from these hierarchical high-level abstractions involves the translation of the high-level controller description into an initial FSM (FIG. 1). Typically, the synthesis is performed as an initial translation step (in which a high-level description 100 is translated into an unoptimized FSM 101) followed by optimization steps (which transform FSM 101 into optimized FSM 102). High-level description 100 is hierarchical in the sense that it has a top-level node 100, with child nodes 105 and 104. This hierarchical organization follows, recursively, for each of the child nodes. Initial FSM 101 comprises, in a general sense, functional logic 106 and register bits 107, wherein all register bits 107 receive the same clock signal. Optimized FSM 102 comprises functional logic 108 and register bits 109. Functional logic 108 is simpler than functional logic 106 and/or register 109 has fewer bits than register 107. Both FSMs 101 and 102 provide the same functionality with respect to the primary inputs and outputs of the FSM.
The translation ensures correct implementation of the high-level semantics into an FSM, and the subsequent optimizations aim to reduce the cost of the implementation while preserving the observable sequential behavior. In conventional systems, the optimizations are performed without any additional guidance from the structure of the high-level description.
For example, classical FSM optimization techniques include state minimization, state assignment, state encoding and sequential circuit level optimizations such as retiming. This separation of the translation and optimization phases leads to the loss of information about the high-level description that is useful for optimization.
Other known methods for optimizing FSMs generated from high-level descriptions use the structure of the high-level representation to determine an over-approximate reachable state set, but do not use the structure of the high-level language directly in the optimization strategy. Some known techniques do in fact use the structure of the input description, however, information about the global reachability and observability is unknown, thus the optimizations are generally local in scope.
It would therefore be desireable to have a method for automatically optimizing FSMs synthesized from high-level descriptions which uses the structure of the high-level description in conjunction with global reachability information in order to select sub-FSMs for optimization which achieve circuits that are more highly optimized.
It would further be desireable to have a method which achieves greater optimization of sub-FSMs by using global reachability information while optimizing a selected sub-FSM.
In circuit synthesis software in accordance with a preferred embodiment of the present invention, finite state machines (FSMs) are translated from hierarchical high-level descriptions and optimized. Optimization involves partitioning. With respect to the hierarchical high-level description a partition is the subtree defined by a selected node. With respect to the translated FSM, a partition is a subset of the next state functions, a subset of the output functions and a subset of the state variables corresponding to the selected subset of functions. Partitions of the FSM are selected by scanning the nodes of the hierarchical description and assigning to each suitable node a metric based upon the reachability function of the FSM. The metric is an indicator of the desirability of using the partition of the FSM, corresponding to the node, as a region of the FSM upon which to apply FSM optimization techniques. Based upon the metric, the software selects certain partitions for optimization. Optimization of a partition can include the steps of converting the partition to a state graph, state graph minimization, state assignment (also known as re-encoding) and conversion back to an FSM. Any hierarchical high-level language is suitable for use with the present invention, provided that a correspondence between nodes of the high-level description and partitions of the FSM can be determined. Conversion of an FSM partition for the purposes of optimization is performed with pruning functions also derived from the FSM""s reachability function.
In general, the invention comprises the following method, the steps of which are performed by a data processing system: scanning at least one node of a hierarchical description of a finite state machine; assigning, for each node of the hierarchical description scanned, a metric determined from a reachability function of the finite state machine; and selecting, according to the metric, certain nodes of the hierarchical description as defining a partition of the finite state machine for optimization.
The invention also comprises the following method, the steps of which are performed by a data processing system: generating at least one state or state transition of a state graph from a finite state machine; and determining whether the state or state transition is valid from the reachability function of the finite state machine.
Furthermore, the invention comprises the following method, the steps of which are performed by a data processing system: assigning a property to an input description; translating the input description into a first finite state machine, wherein the first finite state machine comprises at least a second finite state machine; generating at least one state or state transition of a state graph from the second finite state machine; and determining whether the state or state transition is valid from the property of the input description.